1. Field of the Invention
The present invention relates to a node disjoint path forming method for a hypercube having a damaged node, and particularly, to a node disjoint path forming method for a hypercube having a damaged node which is capable of overcoming a fault tolerance in a topology between processors of a parallel processing computer and searching an n-number of node disjoint paths each having an n-length by avoiding a damaged node, which is known, using a predetermined algorithm.
2. Description of the Conventional Art
Conventionally, an n-dimensional hypercube has a 2.sub.n number of nodes. At this time, each node has an n-number of edges. As one of the important characteristics, the n-dimensional hypercube has an n-number of node disjoint paths having an n-number of lengths. There are known various node disjoint path forming methods. However, the above-described methods are not adapted with respect to the damaged nodes. In order to overcome the above-described problem, the conventional method is first adapted, and then the damaged nodes formed in the node disjoint path are substituted with surplus nodes. Thereafter, if there is a duplicate node the node disjoint characteristic of which is checked, the duplicate node should be substituted. The above-described operation is repeated. In this case, since there are numerous occasions for substituting one node and more than one node at one time, it is very hard to manually check the entire node disjoint characteristic.
A method is disclosed for forming a path by avoiding a damaged node in the hypercube. In more detail, this method is directed to substituting the damaged node based on the damaged condition of the node with respect to one path.